package medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 377. 组合总和 Ⅳ
 * 创建时间：2024-04-22 23:25
 * 地址：https://leetcode.cn/problems/combination-sum-iv/description/
 */
public class 组合总和Ⅳ_377 {
    static class Solution {

        int ans = 0;
        public int combinationSum4(int[] nums, int target) {
            int[] memo = new int[target + 1];
            Arrays.fill(memo, -1);
            return dfs(nums, target, memo);
        }

        int dfs(int[] nums, int left, int[] memo) {
            if (left == 0) {
                return 1;
            }
            if (memo[left] != -1) {
                return memo[left];
            }
            int res = 0;
            for (int num : nums) {
                if (num <= left) {
                    res += dfs(nums, left - num, memo);
                }
            }
            return memo[left] = res;
        }

        public static void main(String[] args) {
            Solution s = new Solution();
            int[] nums = {1, 2, 3};
            System.out.println(s.combinationSum4(nums, 4));
        }
    }
}
